package com.mamingchao.basic.chain;

/**
 * 单向、双向链表的反转
 *
 * Created by mamingchao on 2020/11/14.
 */
public class LinkedListRevert {

    private static class SingleLinkedNode{
        private int value;
        private SingleLinkedNode next;

        public SingleLinkedNode(int value) {
            this.value = value;
        }
    }

    /**
     * 单向链表反转
     * @param head
     * @return
     */
    private static SingleLinkedNode revertSingleLinkedList(SingleLinkedNode head){
        SingleLinkedNode pre = null;
        SingleLinkedNode next = null;

        while(head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }

    private static SingleLinkedNode deleteSpecificValueNode(SingleLinkedNode head,int value){

        //if the head and successors of the head's value is equal to specific value
        //remove the head
        //for example, the linkedList is 3->3->3->4->3->5->null, and the specific value is 3, then the new head's value should be 4
        while (head != null) {
            if (head.value != value){
                break;
            } else {
               head=head.next;
            }
        }

        SingleLinkedNode pre = head;
        SingleLinkedNode cur = head;

        while (cur != null) {
            if (cur.value != value) {
                pre = cur;
            } else {
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return head;
    }






    private class DoubleLinkedNode{
        private int value;
        private DoubleLinkedNode next;
        private DoubleLinkedNode pre;

        public DoubleLinkedNode(int value) {
            this.value = value;
        }
    }

    /**
     * 双向链表反转
     * @param head
     * @return
     */
    private DoubleLinkedNode revertDoubleLinkedList(DoubleLinkedNode head){
        DoubleLinkedNode pre = null;
        DoubleLinkedNode next = null;

        while(head != null) {
            next = head.next;
            head.next=pre;
            head.pre = next;
            pre = head;
            head = next;
        }

        return pre;
    }


    public static void main(String[] args) {
        SingleLinkedNode head = new SingleLinkedNode(1);
        SingleLinkedNode node1= new SingleLinkedNode(2);
        SingleLinkedNode node2= new SingleLinkedNode(3);
        SingleLinkedNode node3= new SingleLinkedNode(4);
        SingleLinkedNode node4= new SingleLinkedNode(5);
        SingleLinkedNode node5= new SingleLinkedNode(6);

        head.next = node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=null;

        SingleLinkedNode newHead = revertSingleLinkedList(head);

        System.out.println(newHead.next.value);

        deleteSpecificValueNode(newHead,5);
        System.out.println(newHead.next.value);

    }
}
